#include<iostream>
#include<vector>
#include<string>
using namespace std;

// 用字符串把结构体表示串起来，可以节省空间和运行时间
// 拼接字符串函数:sprintf_s(s, "M=%d, C=%d, flag=%d", numofchurch, numofwild, flag);

vector<string>visited;
int numOfMissionary;						//在初始位置的传教士数目
int numOfSavage;							//在初始位置的野人数目
int numOfBoat;								//当前船位置，默认1是右，0是左
int totalPlan;								// 总共的解法
vector<vector<string>>option;						// 最佳方法之一
int minPath = 1 << 30;						// 最短路径 

bool isSafe(int M, int C, int boatFlag);	// 检查是否安全
void path(int M, int C, int boatFlag);		//尝试路径
void pickupInfo(string s, char delim, int& missonary, int& savage, int& boat);		// 通过分割字符串获取参数的信息
int  changeType(string s);															// 转换字符串类型为数字
void printGraph(vector<string>);													// 打印路径

int main() {
	cin.tie(0);	//通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。
	ios::sync_with_stdio(false);
	printf("请按序同行输入传教士、野人的数目，船的容量:\n");
	scanf_s("%d%d%d", &numOfMissionary, &numOfSavage, &numOfBoat);
	if (numOfBoat > 1) {
		char s[30];
		sprintf_s(s, "%d_%d_%d", numOfMissionary, numOfSavage, 1);
		visited.push_back(s);
		// 字符串分割参数值
		path(numOfMissionary, numOfSavage, 1);
	}
	printf("\nThe number of  solutions of the  best situation is %d\n", totalPlan);
	if (option.size() > 0) {
		for (int i = 0; i < option.size(); i++) {
			printf("\nThe  %d th of the best ways of solution of the situation is(%d步数):\n", (i+1),option[i].size());
			for (int j = 0; j < option[i].size(); j++) {
				cout << option[i][j];
				if (j < option[i].size() - 1)
					printf("->");
			}
			printf("\n");
		}
	}
	else {
		printf("Failed\n");
	}
}

bool isSafe(int M, int C, int boatFlag) {
	// 1、检查M和C数量是否在范围内
	if (M < 0 || M>numOfMissionary || C < 0 || C>numOfSavage)  return false;
	// 2、检查船的朝向是否为1或0
	if (boatFlag != 1 &&  boatFlag != 0)	return false;
	// 3、检查是否安全, 任何一岸有传教士且传教士人数小于野人人数
	if ((M>0&&M < C) || ((numOfMissionary - M)&& (numOfMissionary - M) < (numOfSavage - C))  ) return false;
	// 4、检查是否重复
	char s[30];
	sprintf_s(s, "%d_%d_%d", M, C, boatFlag);
	for (int i = 0; i < visited.size(); i++) {
		if (s == visited[i])
			return false;
	}
	visited.push_back(s);
	return true;
}

void path(int M, int C, int boatFlag) {
	if (M == 0 && C == 0 && boatFlag == 0) {
		totalPlan++;
		printf("第%2d种方案:共%d步数:", totalPlan, visited.size());
		if (visited.size() <= minPath) {
			minPath = visited.size();
			vector<vector<string>>::iterator it;
			for (it = option.begin(); it != option.end();) {
				if ((*it).size() > minPath)
					it = option.erase(it);
				else
					++it;
			}
			vector<string>tmp = visited;
			option.push_back(tmp);
		}
		for (int i = 0; i < visited.size(); i++) {
			cout << visited[i];
			if (i < visited.size()-1)
				printf("->");
		}
		printf("\n下图示表示过程 @代表传教士,#代表野人，█代表岸边,=代表船只\n");
		printGraph(visited);
		printf("\n\n");
		return;
	}
	// 2层循环，总结了整个过程
	int i, j, k;
	for (i = numOfBoat; i > 0; i--) {						// 本次乘坐船的总人数
		for (j = i; j >= 0; j--) {							// 本次船上的传教士的人数 
			k = i - j;
			// 这里不用理是否在左岸和右岸，直接进入下一层判断是否为安全，把问题一次解决
			if (isSafe(M-j,C-k,boatFlag-1)) {				// 前进
				path(M - j, C - k, boatFlag - 1);
				visited.pop_back();
			}
			else if (isSafe(M + j, C + k, boatFlag + 1)) {	//	回家
				path(M + j, C + k, boatFlag + 1);
				visited.pop_back();
			}
		}
	}
}

void printGraph(vector<string> visited){	// M,C是在出发地数据
	printf("\n");
	for (int i = 0; i < visited.size(); i++) {
		string s = visited.at(i);
		int lm=0, rm=0, ls=0, rs=0, b=1,totalLeft=0,j=0;	// 左边传教士，右边传教士，左边野人，右边野人，船的位置
		int widthOfRiver = 10,widthOfBoat = numOfBoat ;
		pickupInfo(s, '_', rm, rs, b);
		lm = numOfMissionary - rm;
		ls = numOfSavage - rs;
		// 打印左岸的人数
		for (j = 0; j < lm; j++) {
			printf("@ ");
			totalLeft++;
		}
		for (j = 0; j < ls; j++) {
			printf("# ");
			totalLeft++;
		}
		while (totalLeft < (numOfMissionary+numOfSavage) + widthOfRiver) {
			printf("  ");
			totalLeft++;
		}
		// 打印右案的人数
		for ( j = 0; j < rm; j++) {
			printf("@ ");
		}
		for (j = 0; j < rs; j++) {
			printf("# ");
		}

		printf("\n");
		// 打印船只和岸边
		for (j = 0; j < (numOfMissionary + numOfSavage);j++) {
			printf("█");
		}
		if (!b) {
			for (j = 0; j < widthOfBoat; j++) {
				printf("= ");
			}
			for (j = 0; j < widthOfRiver - widthOfBoat; j++) {
				printf("  ");
			}
		}
		else {
			for (j = 0; j < widthOfRiver - widthOfBoat; j++) {
				printf("  ");
			}
			for (j = 0; j < widthOfBoat; j++) {
				printf("= ");
			}
		}
		for (j = 0; j < (numOfMissionary + numOfSavage); j++) {
			printf("█");
		}
		printf("\n\n");
	}
}

void pickupInfo(string s,char delim ,  int& missonary, int& savage, int& boat) {
	vector<string> tokens;
	auto string_find_first_not = [s, delim](size_t pos = 0)->size_t {
		for (size_t i = pos; i < s.size(); i++) {
			if (s[i] != delim)
				return i;
		}
		return string::npos;
	};
	size_t lastPos = string_find_first_not(0);
	size_t pos = s.find(delim, lastPos);
	while (lastPos!=string::npos) {
		tokens.emplace_back(s.substr(lastPos, pos - lastPos));
		lastPos = string_find_first_not(pos);
		pos = s.find(delim, lastPos);
	}	
	missonary = changeType(tokens[0]);
	savage = changeType(tokens[1]);
	boat = changeType(tokens[2]);
}

int changeType(string s) {
	int num=0;
	for (int i = 0;i<= s.size() - 1; i--) {
		num = num * 10 + (int)(s[i]-'0');
	}
	return num;
}